// https://www.lintcode.com/problem/search-a-2d-matrix-ii/

public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        // write your code here
        int ret = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0;
        int j = cols - 1;
        while ((i < rows) && (j >= 0)) {
            if (matrix[i][j] > target) { // target在左面
                j -= 1;
            } else if (matrix[i][j] < target) { // target在下面一行，一开始遇到这种情况肯定j = cols - 1。
                i += 1;
            } else {
                ret += 1;
                i += 1;
                j -= 1; // 因为从上到下是排序的，所以j肯定往左。
            }
        }
        return ret;
    }
}